#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__

/*
===============================================================================

Linked list template
    double linked
===============================================================================
*/

namespace inf {

    template< typename Type >
    class ListNode
    {
    public:
                    ListNode( void ) { next = prev = NULL; }

        Type *		get_prev( void ) const { return prev; }
        Type *		get_next( void ) const { return next; }
        void		set_prev( Type *prev ) { this->prev = prev; }
        void		set_next( Type *next ) { this->next = next; }

    private:
        Type *		next;
        Type *		prev;
    };

    template< typename Type, ListNode<Type> Type::*nodePtr >
    class LinkedList {
    public:
                    LinkedList( void );

        Type *		get_first( void ) { return first; }
        Type *		get_last( void ) { return last; }
        Type *		get_next( Type *element ) { return (element->*nodePtr).get_next(); }
        Type *		get_prev( Type *element ) { return (element->*nodePtr).get_prev(); }

        void		add_to_front( Type *element );
        void		add_to_end( Type *element );
        void		insert_before( Type *element, Type *before );
        void		insert_after( Type *element, Type *after );

        void		remove( Type *element );
        Type *		remove_first( void );

        static void	test( void );

    private:
        Type *		first;
        Type *		last;
    };

    template< typename Type, ListNode<Type> Type::*nodePtr >
    LinkedList<Type,nodePtr>::LinkedList( void ) {
        first = last = NULL;
    }

    template< typename Type, ListNode<Type> Type::*nodePtr >
    void LinkedList<Type,nodePtr>::add_to_front( Type *element ) {
        (element->*nodePtr).set_prev( NULL );
        (element->*nodePtr).set_next( first );
        if ( first ) {
            (first->*nodePtr).set_prev( element );
        }
        first = element;
        if ( last == NULL ) {
            last = element;
        }
    }

    template< typename Type, ListNode<Type> Type::*nodePtr >
    void LinkedList<Type,nodePtr>::add_to_end( Type *element ) {
        (element->*nodePtr).set_prev( last );
        (element->*nodePtr).set_next( NULL );
        if ( last ) {
            (last->*nodePtr).set_next( element );
        }
        last = element;
        if ( first == NULL ) {
            first = element;
        }
    }

    template< typename Type, ListNode<Type> Type::*nodePtr >
    void LinkedList<Type,nodePtr>::insert_before( Type *element, Type *before ) {
        if ( (before->*nodePtr).get_prev() != NULL ) {
            ((before->*nodePtr).get_prev()->*nodePtr).set_next( element );
        } else {
            first = element;
        }
        (element->*nodePtr).set_prev( (before->*nodePtr).get_prev() );
        (element->*nodePtr).set_next( before );
        (before->*nodePtr).set_prev( element );
    }

    template< typename Type, ListNode<Type> Type::*nodePtr >
    void LinkedList<Type,nodePtr>::insert_after( Type *element, Type *after ) {
        if ( (after->*nodePtr).get_next() != NULL ) {
            ((after->*nodePtr).get_next()->*nodePtr).set_prev( element );
        } else {
            last = element;
        }
        (element->*nodePtr).set_prev( after );
        (element->*nodePtr).set_next( (after->*nodePtr).get_next() );
        (after->*nodePtr).set_next( element );
    }

    template< typename Type, ListNode<Type> Type::*nodePtr >
    void LinkedList<Type,nodePtr>::remove( Type *element ) {
        if ( (element->*nodePtr).get_prev() != NULL ) {
            ((element->*nodePtr).get_prev()->*nodePtr).set_next( (element->*nodePtr).get_next() );
        } else {
            first = (element->*nodePtr).get_next();
        }
        if ( (element->*nodePtr).get_next() != NULL ) {
            ((element->*nodePtr).get_next()->*nodePtr).set_prev( (element->*nodePtr).get_prev() );
        } else {
            last = (element->*nodePtr).get_prev();
        }
        (element->*nodePtr).set_prev( NULL );
        (element->*nodePtr).set_next( NULL );
    }

    template< typename Type, ListNode<Type> Type::*nodePtr >
    Type *LinkedList<Type,nodePtr>::remove_first( void ) {
        if ( first == NULL ) {
            return NULL;
        }
        Type *element = first;
        first = (element->*nodePtr).get_next();
        if ( first != NULL ) {
            (first->*nodePtr).set_prev( NULL );
        } else {
            last = NULL;
        }
        return element;
    }

    template< typename Type, ListNode<Type> Type::*nodePtr >
    void LinkedList<Type,nodePtr>::test( void ) {

        class MyType {
        public:
            ListNode<MyType> listNode;
        };

        LinkedList<MyType,&MyType::listNode> myList;

        MyType *element = new MyType;
        myList.add_to_front( element );
        for ( MyType *e = myList.get_first(); e != NULL; e = myList.get_next( e ) ) {
        }
        myList.remove( element );
        delete element;
    }


}   // ::inf

#endif /* !__LINKEDLIST_H__ */
